import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;

public final class MultiLineMove {
	private static final int PIECE_MAX_COUNT = 6;
	private static final int GRID_SHIFT = 10;
	private static final int GRID_MAX_COUNT = 1 << GRID_SHIFT; // 10 => 1024
	private static final int GRID_MASK = GRID_MAX_COUNT - 1;
	private static final String[] MAP;
	private static final int W, H;
	private static final int[] MOVE0, MOVE1, MOVE2, MOVE3; // up, left, right, down
	private static final int PN;
	private static final long OP, TP;
	private static final LongLongHashMap map = new LongLongHashMap(65536, 0.75f);
	private static final LongList list = new LongList(65536);

	static {
		var fileName = System.getProperty("map");
		if (fileName == null) {
			MAP = new String[]{ // o/a => t/a
					"o   x a",
					" x    x",
					"   x   ",
					"x    x ",
					"  x t  ",
					" t  x  ",
					"ox    a",
			};
		} else {
			try {
				MAP = Files.readAllLines(Paths.get(fileName), StandardCharsets.UTF_8).toArray(new String[0]);
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		W = MAP[0].length();
		H = MAP.length;
		int N = Math.multiplyExact(W, H);
		//noinspection ConstantValue
		if (PIECE_MAX_COUNT * GRID_SHIFT > 64 || N <= 0 || N > GRID_MAX_COUNT)
			throw new AssertionError();
		MOVE0 = new int[N];
		MOVE1 = new int[N];
		MOVE2 = new int[N];
		MOVE3 = new int[N];
		long op = 0, tp = 0;
		int i = 0, on = 0, tn = 0, t, j;
		for (int y = 0; y < H; y++) {
			var line = MAP[y];
			if (line.length() != W)
				throw new AssertionError();
			for (int x = 0; x < W; x++, i++) {
				int c = line.charAt(x);
				for (t = y, j = i; ; j -= W)
					if (--t < 0 || MAP[t].charAt(x) == 'x')
						break;
				MOVE0[i] = j;
				for (t = x, j = i; ; j--)
					if (--t < 0 || line.charAt(t) == 'x')
						break;
				MOVE1[i] = j;
				for (t = x, j = i; ; j++)
					if (++t >= W || line.charAt(t) == 'x')
						break;
				MOVE2[i] = j;
				for (t = y, j = i; ; j += W)
					if (++t >= H || MAP[t].charAt(x) == 'x')
						break;
				MOVE3[i] = j;
				if (c == 'o' || c == 'a') {
					op = (op << GRID_SHIFT) + i;
					on++;
				}
				if (c == 't' || c == 'a') {
					tp = (tp << GRID_SHIFT) + i;
					tn++;
				}
			}
		}
		if (on <= 0 || on > PIECE_MAX_COUNT || (on != tn && tn != 0))
			throw new AssertionError();
		PN = on;
		OP = op;
		TP = tn > 0 ? tp : -1;
	}

	private static long normalize(long p) {
		long q = 0, m = Long.MAX_VALUE;
		for (int i = 0, n = GRID_SHIFT * PN; i < n; i += GRID_SHIFT) {
			long a = 0;
			for (int j = 0; j < n; j += GRID_SHIFT) {
				var b = (p >> j) & GRID_MASK;
				if (a < b & b < m)
					a = b;
			}
			m = a;
			q += a << i;
		}
		return q;
	}

	private static boolean search(long p, int[] move, int delta) {
		long q = 0;
		for (int i = 0, n = GRID_SHIFT * PN; i < n; i += GRID_SHIFT) {
			long b = move[(int)(p >> i) & GRID_MASK];
			for (int j = i - GRID_SHIFT; j >= 0; j -= GRID_SHIFT) {
				if (b == ((q >> j) & GRID_MASK)) {
					b -= delta;
					j = i;
				}
			}
			q = (q << GRID_SHIFT) + b;
		}
		q = normalize(q);
		if (map.putIfAbsent(q, p) == -1)
			list.add(q);
		return q == TP;
	}

	public static boolean search() {
		map.clear();
		map.putIfAbsent(OP, -2);
		list.clear();
		list.add(OP);
		if (OP == TP)
			return true;
		for (int i = 0; i < list.size(); i++) {
			var p = list.get(i);
			if (search(p, MOVE0, -W)
					|| search(p, MOVE1, -1)
					|| search(p, MOVE2, 1)
					|| search(p, MOVE3, W))
				return true;
		}
		return false;
	}

	private static void printLine() {
		for (int i = -1; i <= W; i++)
			System.out.print('-');
		System.out.println();
	}

	private static void print(long p) {
		for (int i = 0, y = 0; y < MAP.length; y++) {
			System.out.print('|');
			var line = MAP[y];
			for (int x = 0; x < line.length(); x++, i++) {
				var c = line.charAt(x);
				if (c < 'x') {
					c = ' ';
					for (int j = 0, n = GRID_SHIFT * PN; j < n; j += GRID_SHIFT) {
						if (i == ((p >> j) & GRID_MASK)) {
							c = 'o';
							break;
						}
					}
				}
				System.out.print(c);
			}
			System.out.println('|');
		}
	}

	public static void print() {
		var path = new LongList(64);
		for (var p = TP >= 0 ? TP : list.get(list.size() - 1); p >= 0; p = map.get(p))
			path.add(p);
		for (int n = path.size(), i = n - 1; i >= 0; i--) {
			System.out.println(n - i);
			printLine();
			print(path.get(i));
			printLine();
		}
	}

	public static void main(String[] args) {
		var t = System.nanoTime();
		var r = search();
		t = (System.nanoTime() - t) / 1_000_000;
		print();
		System.out.format("r=%s, list=%d, %dms%n", r, list.size(), t);
	}

	static final class LongList {
		private long[] vs;
		private int n;

		LongList(int cap) {
			vs = new long[cap];
		}

		int size() {
			return n;
		}

		void clear() {
			n = 0;
		}

		long get(int i) {
			return vs[i];
		}

		void add(long v) {
			if (n == vs.length)
				vs = Arrays.copyOf(vs, n << 1);
			vs[n++] = v;
		}
	}

	static final class LongLongHashMap {
		private int size;
		private long[] keyTable;
		private long[] valueTable;
		private long zeroValue;
		private boolean hasZeroValue;
		private final float loadFactor; // (0,1)
		private int threshold;
		private int mask;
		private int shift;

		LongLongHashMap(int cap, float loadFactor) {
			this.loadFactor = loadFactor;
			int tableSize = tableSize(Math.max(cap, 0));
			threshold = (int)(tableSize * loadFactor);
			mask = tableSize - 1;
			shift = Long.numberOfLeadingZeros(mask);
			keyTable = new long[tableSize];
			valueTable = new long[tableSize];
		}

		private int tableSize(int cap) {
			cap = Math.min(Math.max((int)Math.ceil(cap / loadFactor), 2), 1 << 30);
			return 1 << (32 - Integer.numberOfLeadingZeros(cap - 1)); // [0,1<<30] => [0,1,2,4,8,...,1<<30]
		}

		private int hash(long key) {
			return (int)((key * 0x9E3779B97F4A7C15L) >>> shift);
		}

		void clear() {
			if (size == 0)
				return;
			size = 0;
			hasZeroValue = false;
			zeroValue = 0;
			Arrays.fill(keyTable, 0);
		}

		long get(long key) {
			if (key == 0)
				return hasZeroValue ? zeroValue : -1;
			var kt = keyTable;
			int m = mask;
			for (int i = hash(key); ; i = (i + 1) & m) {
				var k = kt[i];
				if (k == key)
					return valueTable[i];
				if (k == 0)
					return -1;
			}
		}

		long putIfAbsent(long key, long value) {
			if (key == 0) {
				var oldV = zeroValue;
				if (!hasZeroValue) {
					hasZeroValue = true;
					zeroValue = value;
					size++;
				}
				return oldV;
			}
			var kt = keyTable;
			var vt = valueTable;
			int m = mask;
			for (int i = hash(key); ; i = (i + 1) & m) {
				var k = kt[i];
				if (k == 0) {
					kt[i] = key;
					vt[i] = value;
					if (++size >= threshold)
						resize(kt.length << 1);
					return -1;
				}
				if (k == key)
					return vt[i];
			}
		}

		private void resize(int newSize) { // [1,2,4,8,...,0x4000_0000]
			threshold = (int)(newSize * loadFactor);
			int m = newSize - 1;
			mask = m;
			shift = Long.numberOfLeadingZeros(m);
			var kt = new long[newSize];
			var vt = new long[newSize];
			if (size != 0) {
				var oldKt = keyTable;
				var oldVt = valueTable;
				for (int j = 0, n = oldKt.length; j < n; j++) {
					var k = oldKt[j];
					if (k != 0) {
						for (int i = hash(k); ; i = (i + 1) & m) {
							if (kt[i] == 0) {
								kt[i] = k;
								vt[i] = oldVt[j];
								break;
							}
						}
					}
				}
			}
			keyTable = kt;
			valueTable = vt;
		}
	}
}
